//
// Created by Vincent_Vic on 2020/3/30.
//

#ifndef DATAORGANIZATION_INDEXMAXHEAP_H
#define DATAORGANIZATION_INDEXMAXHEAP_H

#include <algorithm>
#include <cassert>

template <typename Item>
class IndexMaxHeap {
private:
    Item* data;
    //索引
    int* indexs;
    //反向查找
    int*  rev;
    int count ;
    int capacity;

    void shiftUp(int k){
        //indexheap 修改地方
        while( k> 1 && data [indexs[k / 2]] < data[indexs[k]]){ //判断父节是否小于k节点
            std::swap(indexs[k/2], indexs[k]); //调整位置
            rev[indexs[k/2]] = k/2;
            rev[indexs[k]] = k;
            k /= 2 ; //进入父节点继续检查调整后的父节点
        }
    }

    void shiftDown(int k){
        while( 2*k <= count){ //判断是否有左孩子就说明可以继续判断
            // 在此轮循环中，data[k]和data[j]交换位置
            // 初始化为父节点与左孩子交换位置j
            int j = 2 * k;
            //右孩子存在并且大于父节点，交换位置j改成右孩子
            if(j + 1 <= count && data[indexs[j+1]] > data[indexs[j]]) j ++;
            //如果父节点大于等于要交换的节点，那么无需操作
            if( data[indexs[k]] >= data[indexs[j]] ) break;
            std::swap(indexs[k], indexs[j]); //调整位置
            rev[indexs[k]] = k;
            rev[indexs[j]] = j;
            k = j ; //进入子节点继续检查调整后的子节点
        }
    }

public:

    IndexMaxHeap(int capacity){
        this->capacity = capacity;
        indexs= new int [capacity+1];
        rev = new int[capacity+1];
        for (int i = 0; i <= capacity; ++i) {
            rev[i] = 0;
        }
        data = new Item[capacity + 1];
        count = 0;
    }

    //Heapify版本
    IndexMaxHeap(Item arr[],int n){
        data = new Item[n+1];
        count = capacity = n;
        for (int i = 0; i < n; ++i)
            data[i+1] = arr[i];
        for (int i = count / 2; i >= 1 ; --i)
            shiftDown(i);
    }

    virtual ~IndexMaxHeap() {
        delete[] data;
        data = nullptr ;
        delete[] indexs;
        indexs = nullptr ;
        delete[] rev;
        rev = nullptr ;
    }

    int size(){
        return count;
    }

    int getCapacity(){
        return capacity;
    }

    bool isEmpty(){
        return count == 0 ;
    }

    bool contain(int i){
        assert(i+1>= 1 && i+1 <= capacity);
        return rev[i+1] !=0;
    }

    // i 面向用户从0开始的索引，内部从1开始
    bool insert(int i,Item item){
        if( capacity == count || (i+1 >= 1 && i+1 <= capacity) )
            return false; //堆满这里false,也可以可以开辟新的空间
        //最小索引堆修改的内容
        i++;
        data[i] = item; //插入元素
        indexs[count+1] = i;

        rev[i] =count + 1;
        //调整位置
        shiftUp(count);
        return true;
    }

    Item extractMax(){
        assert( count > 0); //防止二叉堆中没有数据
        Item ret = data[indexs[1]]; //取出最大值
        std::swap(indexs[1],indexs[count--]); //将最后一个元素移动到队首
        rev[indexs[1]] = 1;
        rev[indexs[count]] = 0;
        shiftDown(1); //向下调整
        return ret;
    }

    Item extractMaxIndex(){
        assert( count > 0); //防止二叉堆中没有数据
        Item ret = indexs[1] - 1; //取出最大值
        std::swap(indexs[1],indexs[count--]); //将最后一个元素移动到队首
        rev[indexs[1]] = 1;
        rev[indexs[count]] = 0;
        shiftDown(1); //向下调整
        return ret;
    }

    Item getItem(int i){
        return data[i+1];
    }

    //改变堆的元素
    void change(int i,Item newItem){
        i++;
        data[i] = newItem;
        //找到indexs[j] = i,j表示data[i[在堆中的位置
        //之后up,再down
//        for (int j = 1; j <= count; ++j) {
//            if (indexs[j] == i ){
//                shiftUp(j);
//                shiftDown(j);
//            }
//        }
        //加入反向查找
        int j=rev[i];
        shiftUp(j);
        shiftDown(j);
    }
};


#endif //DATAORGANIZATION_MAXHEAP_H
